class Solution {
public:
bool col[9],dg[20],udg[20];
vector<vector<string>> res;
vector<string> board;
    void dfs(int n,int pos)
    {
        if(pos==n)
        {
            res.push_back(board);
            return;
        }

        for(int i=0;i<n;++i)
        {
            if(!col[i]&&!dg[i+pos]&&!udg[n-i+pos])
            {
                col[i]=dg[i+pos]=udg[n-i+pos]=true;
                board[i][pos]='Q';
                dfs(n,pos+1);
                col[i]=dg[i+pos]=udg[n-i+pos]=false;
                board[i][pos]='.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        board.resize(n);
        for(int i=0;i<n;++i)
        {
            board[i].append(n,'.');
        }
        dfs(n,0);
        return res;
    }
};